package com.zwj.interview.回文结构;

/**
 * 给定一个字符串，请判断如果最多从字符串中删除一个字符能不能得到一个回文字符串。
 * 例如，如果输入字符串"abca"，由于删除字符'b'或'c'就能得到一个回文字符串，因此输出为true
 */
public class DeleteALetterToPalindrome {

    /**
     * 首尾双指针i,j。
     * <p>
     * 当i、j指向的元素相等时，同时往前走。知道碰头或者不相等。
     * <p>
     * 当不相等时，判断去掉i或者去掉j之后的字符串是否为回文串。
     *
     * @param s
     * @return
     */
    public boolean validPalindrome(String s) {
        if (s == null || s.length() <= 2) {
            return true;
        }
        char[] ch = s.toCharArray();
        int i = 0;
        int j = ch.length - 1;
        while (i < j) {
            if (ch[i] != ch[j]) {
                //ch[i]!=ch[j]说明i到j不是回文串，那么就要缩短一个字符的距离再来判断是不是回文串
                return isPalindrome(ch, i+1, j) || isPalindrome(ch, i, j - 1);
            }
            i++;
            j--;
        }
        return true;
    }




    /**
     * 判断字串是不是回文结构，不断推进两个指针
     * @param ch
     * @param begin
     * @param end
     * @return
     */
    public boolean isPalindrome(char[] ch, int begin, int end) {
        while (begin < end) {
            if (ch[begin] != ch[end]) {
                return false;
            } else {
                begin++;
                end--;
            }
        }
        return true;
    }


}
